#define _CRT_SECURE_NO_WARNINGS
#include"add.h"

void STInit(ST* ps) {
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void STPush(ST* ps,int x) {
	if (ps->top == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		int* tmp = (int*)realloc(ps->a, newcapacity * 4);
		if (tmp == NULL) {
			perror("realloc failed");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps) {
	ps->top--;
}
int STTop(ST* ps) {
	return ps->a[ps->top - 1];
}
int STEmpty(ST* ps) {
	if (ps->top == 0)
		return 1;
	return 0;
}
void Swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}


void AdJustDown(int* a, int n, int parent) {
	int child = parent * 2 + 1;
	while (child < n) {
		if (child + 1 < n && a[child] < a[child + 1]) {
			child++;
		}
		if (a[parent] < a[child]) {
			Swap(&a[parent], &a[child]);
			parent = child;
			child = child * 2 + 1;
		}
		else {
			break;
		}

	}
}

void HeapSort(int* a, int n) {
	for (int i = (n - 2) / 2; i >= 0; i--) {
		AdJustDown(a, n, i);
	}
	for (int i = n - 1; i > 0; i--) {
		int tmp = a[i];
		a[i] = a[0];
		a[0] = tmp;
		AdJustDown(a, i, 0);
	}
}


void InsertSort(int* a, int n) {
	for (int i = 1; i < n; i++) {
		int tmp = a[i];
		int end = i - 1;
		while (end >= 0) {
			if (a[end] > tmp) {
				a[end + 1] = a[end];
			}
			else {
				break;
			}
			end--;
		}
		a[end + 1] = tmp;
	}
}


void BubbleSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++) {
		int exchange = 0;
		for (int j = 0; j < n - 1 - i; j++) {
			if (a[j] > a[j + 1]) {
				Swap(&a[j], &a[j + 1]);
				exchange = 1;
			}
		}
		if (exchange == 0) {
			break;
		}
	}
}

void SelectSort(int* a, int n) {
	int start = 0;
	int end = n - 1;
	while (start < end) {
		int maxi = start;
		int mini = start;
		for (int i = start + 1; i <= end; i++) {
			if (a[i] > a[maxi]) {
				maxi = i;
			}
			if (a[i] < a[mini]) {
				mini = i;
			}
		}
		Swap(&a[start], &a[mini]);
		if (start == maxi) {
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		start++;
		end--;
	}
}